/*
 * Copyright (C), 2015-2018
 * FileName: Solution2
 * Author:   zhao
 * Date:     2018/10/8 12:55
 * Description: 两数相加2
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈两数相加2〉
 *
 * @author zhao
 * @date 2018/10/8 12:55
 * @since 1.0.1
 */
public class Solution2 {

  /**************************************
   * 题目
   给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

   你可以假设除了数字 0 之外，这两个数字都不会以零开头。

   示例：

   输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
   输出：7 -> 0 -> 8
   原因：342 + 465 = 807
   **************************************/

  /**************************************
   *
   * 想法：
   *    依次往后循环
   *      相加2个数，判断是否进位
   *
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *
   * ***********************************/
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode next1 = l1;
    ListNode next2 = l2;
    int count = 0;
    boolean carry = false;

    ListNode result = new ListNode(0);
    ListNode runResult = result;

    ListNode preNode = result;

    while (next1 != null || next2 != null) {
      int val1 = next1 == null ? 0 : next1.val;
      int val2 = next2 == null ? 0 : next2.val;

      int tmp = val1 + val2;
      if (carry) {
        tmp++;
      }

      int nodeVal = tmp % 10;
      carry = tmp >= 10;

      if (count == 0) {
        runResult.val = nodeVal;
      } else {
        runResult = new ListNode(nodeVal);
      }
      preNode.next = runResult;

      next1 = next1 == null ? null : next1.next;
      next2 = next2 == null ? null : next2.next;
      preNode = runResult;
      runResult = runResult.next;
      count++;
    }

    if (carry) {
      preNode.next = new ListNode(1);
      preNode = preNode.next;
    }
    preNode.next = null;

    return result;

  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public ListNode better(ListNode l1, ListNode l2) {

    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
      int x = (p != null) ? p.val : 0;
      int y = (q != null) ? q.val : 0;
      int sum = carry + x + y;
      carry = sum / 10;
      curr.next = new ListNode(sum % 10);
      curr = curr.next;
      if (p != null) {
        p = p.next;
      }
      if (q != null) {
        q = q.next;
      }
    }
    if (carry > 0) {
      curr.next = new ListNode(carry);
    }
    return dummyHead.next;

  }
}
